package com.demo.java.OD201_250.OD202;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【RSA 加密算法，素数之积】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145904762
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();  // 输入数字
        int x = -1, y = -1;  // 初始化素数因数，若找不到则为 -1
        double sqrt = Math.sqrt(num);  // 计算数字的平方根，优化搜索范围

        // 从平方根往下遍历，寻找因数
        for (int i = (int) sqrt; i >= 2; i--) {
            if (num % i == 0) {  // 如果 i 是 num 的因数
                int factor1 = i;  // 因数1
                int factor2 = num / i;  // 因数2
                // 判断两个因数是否都为素数
                if (isPrime(factor1) && isPrime(factor2)) {
                    x = factor1;  // 第一个素数因数
                    y = factor2;  // 第二个素数因数
                    break;  // 找到结果后退出循环
                }
            }
        }
        System.out.println(x + " " + y);  // 输出结果
    }

    // 判断一个数字是否为素数
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;  // 小于等于1的数字不是素数
        }
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {  // 如果能被 i 整除，说明不是素数
                return false;
            }
        }
        return true;  // 如果没有找到其他因数，则是素数
    }
}